package tree;

import java.util.Arrays;

/**
 * @author : Rookie
 * @description : 从中序和后续遍历恢复二叉树
 * @date : 2023/10/23
 */
public class BinaryTreeRestore {

    public static void main(String[] args) {
        int[] inorder = new int[] {9,3,15,20,7};
        int[] postorder = new int[] {9,15,7,20,3};
        TreeNode root = buildTree(inorder, postorder);
        BinaryTreeUtil.Traversal.sequenceTraversal(root);
    }

    private static TreeNode buildTree(int[] inorder,int[] postorder) {
        if (postorder.length == 0) {
            return null;
        }
        // 取后序遍历最后一个节点 就是根节点
        int rootVal = postorder[postorder.length-1];
        TreeNode root = new TreeNode(rootVal);

        // 寻找切割点
        int index;
        for (index = 0; index < inorder.length; index++) {
            if (inorder[index] == rootVal) {
                break;
            }
        }
        // 切割中序数组 得到左子树中序和右子树中序
        // 中序切割点左侧最后一个值
        int cutPointVal = 0;
        int rightIndex = 0;
        int[] leftInorder = new int[index];
        int[] rightInorder = new int[inorder.length-index-1];
        for (int i=0;i<inorder.length;i++) {
            if (i < index) {
                leftInorder[i] = inorder[i];
                if (i == index-1) {
                    cutPointVal = inorder[i];
                }
            }
            if (i>index) {
                rightInorder[rightIndex++] = inorder[i];
            }
        }
        System.out.println("左子树中序：" + Arrays.toString(leftInorder));
        System.out.println("右子树中序：" + Arrays.toString(rightInorder));
        rightIndex = 0;
        // 切割后序数组 得到左子树后续和右子树后序
        int cutPointIndex;
        for (cutPointIndex = 0; cutPointIndex < postorder.length; cutPointIndex++) {
            if (cutPointVal == postorder[cutPointIndex]) {
                break;
            }
        }
        int[] leftPostOrder = new int[cutPointIndex];
        int[] rightPostOrder = new int[postorder.length - cutPointIndex - 1];

        for (int i = 0; i < postorder.length-cutPointIndex; i++) {
            if (i < cutPointIndex) {
                leftPostOrder[i] = postorder[i];
            }
            if (i>cutPointIndex) {
                rightPostOrder[rightIndex++] = postorder[i];
            }
        }
        System.out.println("左子树后续：" + Arrays.toString(leftPostOrder));
        System.out.println("右子树后续：" + Arrays.toString(rightPostOrder));
        // 遍历左子树
        root.left = buildTree(leftInorder,leftPostOrder);
        root.right = buildTree(rightInorder,rightPostOrder);
        // 遍历右子树
        return root;
    }
}
